/*
剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

 

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
 

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
 

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
 

注意：本题与主站 209 题相同：https://leetcode-cn.com/problems/minimum-size-subarray-sum/
*/
#include <vector>
#include<climits>
#include<algorithm>
using namespace std;
class Solution {
public:
    //滑动窗口解决方案
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ans = INT_MAX;
        int start = 0;
        int end = 0;
        int sum = 0;
        while(end < n)
        {
            sum += nums[end];
            //slide window,when sum >= target
            //thrink the window from start
            while(sum >= target)
            {
                int length = end - start + 1;
                ans = ans > length ? length:ans;
                sum -= nums[start];
                ++start;
            }
            ++end;
        }

        return ans == INT_MAX ? 0 : ans;
    }

    //12/15/2019 23:30 提交
    //本质也是一种滑动窗口
    int minSubArrayLen2(int target, vector<int>& nums)
    {
        int startPos = 0;
        int minLength = INT_MAX;
        int sum = 0;
        for(size_t i = 0;i < nums.size();++i)
        {
            sum += nums[i];
            if(sum >= target)
            {
                int tmpSum = sum;
                while(tmpSum >= target)
                {
                    tmpSum -= nums[startPos++];
                }
                int length = i - (startPos - 1) + 1;
                if(minLength > length)
                {
                    minLength = length;
                }
                sum = tmpSum;
            }        
        }
        
        return minLength == INT_MAX ? 0 : minLength;
    }

    //
    /*
    得到前缀和之后，对于每个开始下标 ii，可通过二分查找得到大于或等于 ii 的最小下标 bound，
    使得 sums[bound]−sums[i−1]≥s，并更新子数组的最小长度（此时子数组的长度是 bound−(i−1)）
    */
    int minSubArrayLen3(int target, vector<int>& nums)
    {
        int n = nums.size();
        int result = INT_MAX;
        vector<int> sums(n+1);
        sums[0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            sums[i] = sums[i-1] + nums[i-1];
        }

        for(int i = 1;i <= n; ++i)
        {
            // sums[xxx] - sums[i-1] == target,sums[xxx] == bound;
            int to_find = target + sums[i-1];
            auto bound = lower_bound(sums.begin(),sums.end(),to_find);
            if(bound != sums.end())
            {
                result = min(result,static_cast<int>(bound - (sums.begin() + i - 1)));
            }
        }

        return result == INT_MAX ? 0 : result;
    }
};